/*
 * Copyright (c) Huawei Technologies Co., Ltd. 2022-2022. All rights reserved.
 * Description: 性能评估器相关源文件
 * Author: sunzhepeng
 * Create: 2022-8-1
 */

#include "topo_detect.h"
#include "evaluator_log_def.h"

namespace HcclEvaluator {

bool TopoDetect::IsConnected(AdjacencyMatrix<> &adjaMatrix, u32 srcNodeIndex, u32 dstNodeIndex)
{
    return adjaMatrix.IsConnected(srcNodeIndex, dstNodeIndex);
}

HcclResult TopoDetect::Detect(AdjacencyMatrix<> &adjaMatrix, std::vector<AdjacencyMatrix<>> &topoMatrixes)
{
    EVALUATOR_CHK_RET(GetConnectedSubGraph(adjaMatrix, topoMatrixes));
    EVALUATOR_INFO("find [%u] subGraph\n", topoMatrixes.size());
    for (auto &topoMatrix : topoMatrixes) {
        AdjaMatrixAttr attr = AdjaMatrixAttr::NOT_DETECT;
        bool isAllConnect = true;
        bool isFullMesh = true;
        TimePoint start = TimeNow();
        EVALUATOR_CHK_RET(TestFullMesh(topoMatrix, isAllConnect, isFullMesh));
        EVALUATOR_INFO("TestFullMesh duration = %lld us\n", DurationUs(TimeNow() - start));
        if (isAllConnect) {
            if (isFullMesh) {
                attr = AdjaMatrixAttr::FULL_MESH;
            } else {
                attr = AdjaMatrixAttr::STAR;
            }
        } else {
            std::vector<std::vector<u32>> paths;
            TimePoint start = TimeNow();
            EVALUATOR_CHK_RET(FindAllHamCycle(topoMatrix, paths));
            EVALUATOR_INFO("FindAllHamCycle duration = %lld us\n", DurationUs(TimeNow() - start));
            u32 ringNum = paths.size();
            if (ringNum == 1) {  // 大环数为1则为单环
                attr = AdjaMatrixAttr::RING;
            } else if (ringNum == 2) {  // 特殊处理，大环数为2则为多环算法（910A）
                attr = AdjaMatrixAttr::MULTI_RING;
            } else {
                attr = AdjaMatrixAttr::NO_TOPO;
            }
        }
        topoMatrix.SetAttr(attr);
        EVALUATOR_INFO("topo is [%u]\n", static_cast<u32>(attr));
    }
    return HCCL_SUCCESS;
}

HcclResult TopoDetect::TestFullMesh(AdjacencyMatrix<> &topoMatrix, bool &isAllConnect, bool &isFullMesh)
{
    isAllConnect = true;
    isFullMesh = true;
    u32 nodeNum = topoMatrix.GetNodeNum();
    std::unordered_set<int> portUsed;

    auto testUniquePort = [](std::unordered_set<int> &portUsed, AdjacencyMatrix<> &topoMatrix, u32 i, u32 j) {
        bool isUniquePort = false;
        AdjaMatrixEdge edge = topoMatrix.GetEdgeByIndex(i, j);
        HcclPort *port = edge.ports;
        while (port) {
            if (portUsed.find(port->portId) == portUsed.end()) {
                isUniquePort = true;
                portUsed.insert(port->portId);
                break;
            }
            port = port->next;
        }
        return isUniquePort;
    };

    for (u32 i = 0; i < nodeNum; i++) {
        portUsed.clear();
        for (u32 j = 0; j < nodeNum; j++) {
            if (i == j) {
                continue;
            }

            if (!IsConnected(topoMatrix, i, j)) {
                isAllConnect = false;
                isFullMesh = false;
                return HCCL_SUCCESS;
            }

            if (isFullMesh) {
                isFullMesh = isFullMesh && testUniquePort(portUsed, topoMatrix, i, j);
            }
        }
    }
    return HCCL_SUCCESS;
}

HcclResult TopoDetect::GetConnectedSubGraph(AdjacencyMatrix<> &adjaMatrix, std::vector<AdjacencyMatrix<>> &topoMatrixes)
{
    std::vector<std::vector<u32>> ConnectedNodeVec;
    TimePoint start1 = TimeNow();
    EVALUATOR_CHK_RET(GetConnectedNode(adjaMatrix, ConnectedNodeVec));
    EVALUATOR_INFO("BFS duration = %lld us\n", DurationUs(TimeNow() - start1));

    TimePoint start = TimeNow();
    topoMatrixes.resize(ConnectedNodeVec.size());
    for (u32 index = 0; index < ConnectedNodeVec.size(); index++) {
        EVALUATOR_CHK_RET(topoMatrixes[index].InitMatrixByList(ConnectedNodeVec[index]));
        u32 sizeBlock = 4;  // block大小为4
        u32 numBlock = topoMatrixes[index].GetNodeNum() / sizeBlock;
        for (u32 i = 0; i < topoMatrixes[index].GetNodeNum(); i++) {
            for (u32 j = 0; j < numBlock; j++) {
                EVALUATOR_CHK_RET(topoMatrixes[index].AddEdgeByIndex(i, j * sizeBlock,
                    adjaMatrix.GetEdgeByIndex(i, j * sizeBlock)));
                EVALUATOR_CHK_RET(topoMatrixes[index].AddEdgeByIndex(i,
                    j * sizeBlock + 1, adjaMatrix.GetEdgeByIndex(i, j * sizeBlock + 1)));  // block展开1
                EVALUATOR_CHK_RET(topoMatrixes[index].AddEdgeByIndex(i,
                    j * sizeBlock + 2, adjaMatrix.GetEdgeByIndex(i, j * sizeBlock + 2)));  // block展开2
                EVALUATOR_CHK_RET(topoMatrixes[index].AddEdgeByIndex(i,
                    j * sizeBlock + 3, adjaMatrix.GetEdgeByIndex(i, j * sizeBlock + 3)));  // block展开3
            }
            for (u32 j = numBlock * sizeBlock; j < topoMatrixes[index].GetNodeNum(); j++) {
                EVALUATOR_CHK_RET(topoMatrixes[index].AddEdgeByIndex(i, j, adjaMatrix.GetEdgeByIndex(i, j)));
            }
        }
    }
    EVALUATOR_INFO("SubGraph duration = %lld us\n", DurationUs(TimeNow() - start));
    return HCCL_SUCCESS;
}

HcclResult TopoDetect::GetConnectedNode(AdjacencyMatrix<> &adjaMatrix, std::vector<std::vector<u32>> &ConnectedNodeVec)
{
    u32 unvisitedFlag = 0xffffffff;
    u32 nodeNum = adjaMatrix.GetNodeNum();
    std::vector<u32> nodeList = adjaMatrix.GetNodeList();
    std::vector<u32> visited(nodeNum, unvisitedFlag);
    PseudoQueue queue(nodeNum, unvisitedFlag);
    u32 numSubGraph = 0;

    for (u32 i = 0; i < nodeNum; i++) {
        if (visited[i] == unvisitedFlag) {
            queue.data[queue.tail++] = i;
            visited[i] = numSubGraph;
            AdjacencyMatrixBFS(adjaMatrix, queue, visited, numSubGraph);
            numSubGraph++;
        }
    }

    ConnectedNodeVec.resize(numSubGraph);
    for (u32 index = 0; index < visited.size(); index++) {
        ConnectedNodeVec[visited[index]].push_back(nodeList[index]);
    }

    return HCCL_SUCCESS;
}

HcclResult TopoDetect::AdjacencyMatrixBFS(AdjacencyMatrix<> &adjaMatrix, PseudoQueue &queue,
    std::vector<u32> &visited, u32 numSubGraph)
{
    u32 unvisitedFlag = 0xffffffff;
    u32 nodeNum = adjaMatrix.GetNodeNum();
    while (queue.head != queue.tail) {
        u32 u = queue.data[queue.head++];
        for (u32 v = 0; v < nodeNum; v++) {
            if (visited[v] == unvisitedFlag && IsConnected(adjaMatrix, u, v)) {
                queue.data[queue.tail++] = v;
                visited[v] = numSubGraph;
            }
        }
    }
    return HCCL_SUCCESS;
}

HcclResult TopoDetect::RemoveHamCycle(AdjacencyMatrix<> &adjaMatrix, std::vector<u32> &path)
{
    for (size_t i = 1; i < path.size(); i++) {
        EVALUATOR_CHK_RET(adjaMatrix.RemoveEdgeByIndex(path[i - 1], path[i]));
        EVALUATOR_CHK_RET(adjaMatrix.RemoveEdgeByIndex(path[i], path[i - 1]));
    }
    EVALUATOR_CHK_RET(adjaMatrix.RemoveEdgeByIndex(path[0], path[path.size() - 1]));
    EVALUATOR_CHK_RET(adjaMatrix.RemoveEdgeByIndex(path[path.size() - 1], path[0]));
    return HCCL_SUCCESS;
}

HcclResult TopoDetect::FindHamCyclePos(AdjacencyMatrix<> &adjaMatrix, std::vector<u32> &path, u32 index, bool &found)
{
    u32 nodeNum = adjaMatrix.GetNodeNum();
    // 递归退出条件，检测到最后一个节点且首尾相连
    if (index == nodeNum) {
        found = IsConnected(adjaMatrix, path[index - 1], 0);
        return HCCL_SUCCESS;
    }

    for (u32 i = 0; i < nodeNum; i++) {
        bool isVisited = false;
        for (u32 j = 0; j < index; j++) {
            if (i == path[j]) {
                isVisited = true;
                break;
            }
        }

        if (!isVisited && IsConnected(adjaMatrix, path[index - 1], i)) {
            path[index] = i;
            EVALUATOR_CHK_RET(FindHamCyclePos(adjaMatrix, path, index + 1, found));
            if (found) {
                return HCCL_SUCCESS;
            }
            path[index] = ERR_NODE;
        }
    }
    found = false;
    return HCCL_SUCCESS;
}

HcclResult TopoDetect::FindHamCycle(AdjacencyMatrix<> &adjaMatrix, std::vector<u32> &path, bool &found)
{
    u32 nodeNum = adjaMatrix.GetNodeNum();
    if (nodeNum > 16) {  // 节点个数大于16时，直接返回不存在大环
        found = false;
        return HCCL_SUCCESS;
    }
    path = std::vector<u32>(nodeNum, ERR_NODE);
    path[0] = 0;  // 大环可以从任意起点开始，此处从0开始
    EVALUATOR_CHK_RET(FindHamCyclePos(adjaMatrix, path, 1, found));  // 从index=1开始递归
    return HCCL_SUCCESS;
}

HcclResult TopoDetect::FindAllHamCycle(AdjacencyMatrix<> adjaMatrix, std::vector<std::vector<u32>> &paths)
{
    while (true) {
        bool found = false;
        std::vector<u32> path;
        EVALUATOR_CHK_RET(FindHamCycle(adjaMatrix, path, found));
        if (!found) {
            break;
        }
        paths.push_back(path);
        EVALUATOR_CHK_RET(RemoveHamCycle(adjaMatrix, path));
    }
    return HCCL_SUCCESS;
}

} // namespace HcclEvaluator